package org.example.three.search;


import javax.swing.*;
import java.io.PrintStream;

/**
 * 二分查找（基于有序数组）
 */
public class BinarySearchST<Key extends Comparable<Key> ,Value> {
    private Key[] keys;
    private Value[] vals;
    private int N;
    public BinarySearchST(int capacity){
        keys = (Key[]) new Comparable[capacity];
        vals = (Value[]) new Object[capacity];
    }
    public int size(){
        return N;
    }
    public Value get(Key key){
        if (isEmpty()){
            return null;
        }
        int i = rank(key);
        if (i<N&& keys[i].equals(key)){
            return vals[i];
        }else {
            return null;
        }
    }
    public int rank(Key key){
        int lo = 0;
        int hi = N-1;
        while (lo<=hi){
            int mid = lo+(hi-lo)/2;
            int cmp = keys[mid].compareTo(key);
            if (cmp>0){
                hi=mid-1;
            }else if(cmp<0){
                lo=mid+1;
            }else {
                return mid;
            }
        }
        return lo;
    }
    public void put(Key key, Value val){
        //查找键，找到则更新值，未找到则新增
        int i = rank(key);
        if (i < N && keys[i].equals(key)){
            vals[i]=val;
            return;
        }
        for(int j = N ; j > i ; j--){
            keys[j]=keys[j-1];
            vals[j]=vals[j-1];
        }
        keys[i]=key;
        vals[i]=val;
        N++;
    }
    public void delete(Key key){

    }
    public boolean isEmpty(){
        return N==0;
    }
}
